package test;

import java.util.*;

/**
 * 描述：
 *      最接近原点的k个点
 * @author hl
 * @version 1.0
 * @date 2020/11/9 9:28
 */
public class KClosest {
    public int[][] kCloset(int[][] points, int K){
        //大根堆
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0];
            }
        });
        for (int i = 0; i < K; i++) {
            queue.offer(new int[] {points[i][0] * points[i][0] + points[i][1] * points[i][1], i});
        }
        for (int i = K; i < points.length; i++) {
            int dest = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            if (dest < queue.peek()[0]) {
                queue.poll();
                queue.offer(new int[]{dest, i});
            }
        }
        int[][] resArr = new int[K][2];
        for (int i = 0; i < K; i++) {
            resArr[i] = points[queue.poll()[1]];
        }
        return resArr;
    }
}
